package com.xaicode.algorithm.leetcode._101_200;

import com.xaicode.utils.StdOut;
import com.xaicode.utils.Stopwatch;

/**
 * <a href="https://leetcode-cn.com/problems/move-zeroes">移动零</a>
 *
 * <p>给定一个数组 <code>nums</code>，编写一个函数将所有 <code>0</code> 移动到数组的末尾，同时保持非零元素的相对顺序。</p>
 *
 * <p><strong>示例:</strong></p>
 *
 * <pre><strong>输入:</strong> <code>[0,1,0,3,12]</code>
 * <strong>输出:</strong> <code>[1,3,12,0,0]</code></pre>
 *
 * <p><strong>说明</strong>:</p>
 *
 * <ol>
 * 	<li>必须在原数组上操作，不能拷贝额外的数组。</li>
 * 	<li>尽量减少操作次数。</li>
 * </ol>
 *
 * @author Locker xaicode@sina.com
 * @version 1.0
 * @date 2021/12/9 0009 22:37
 */
public class _283_Easy_MoveZeroes {

    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};

//        moveZeros(nums);

        Stopwatch.printElapsedTime(o -> moveZeros2(nums));
    }

    /**
     * 双指针
     *
     * <p>创建两个指针<code>i</code>和<code>j</code>，
     * 第一次遍历的时候指针<code>j</code>用来记录当前有多少<code>非0</code>元素。
     * 即遍历的时候每遇到一个<code>非0</code>元素就将其往数组左边挪，
     * 第一次遍历完后，<code>j</code>指针的下标就指向了最后一个<code>非0</code>元素下标。<br>
     * 第二次遍历的时候，起始位置就从<code>j</code>开始到结束，将剩下的这段区域内的元素全部置为<code>0</code>。
     */
    public static void moveZeros(int[] nums) {
        if (nums == null) {
            return;
        }
        // 第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        // 非0元素统计完了，剩下的都是0了，第二次遍历把末尾的元素都赋为0即可
        for (int i = j; i < nums.length; i++) {
            nums[i] = 0;
        }

        StdOut.printsln(nums);
    }

    /**
     * 一次遍历
     *
     * <p>参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点<code>x</code>，
     * 然后把所有小于等于<code>x</code>的元素放到x的左边，大于x的元素放到其右边。<br>
     * 这里我们可以用<code>0</code>当做这个中间点，
     * 把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。<br>
     * 这的中间点就是<code>0</code>本身，
     * 所以实现起来比快速排序简单很多，我们使用两个指针<code>i</code>和<code>j</code>，
     * 只要<code>nums[i]!=0</code>，我们就交换<code>nums[i]</code>和<code>nums[j]</code>
     */
    public static void moveZeros2(int[] nums) {
        if (nums == null) {
            return;
        }
        // two pointers
        int j = 0;

        // solution1: swap two value
//        for (int i = 0; i < nums.length; i++) {
//            // 当前元素!=0，就把其交换到左边，等于0的交换到右边
//            // if current does not equal with 0, swap it to the left, and those equal to 0 swap it to the right
//            if (nums[i] != 0) {
//                int tmp = nums[i];
//                nums[i] = nums[j];
//                nums[j++] = tmp;
//            }
//        }

        // solution2: position judgment
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                if (i > j) {
                    nums[j] = nums[i];
                    nums[i] = 0;
                }
                j++;
            }
        }

        StdOut.printsln(nums);
    }

}
